package com.hspedu.newData.力扣周赛;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-04 
 * @Version: 1.0
 */

public class Test {

    public static int minTravelTime(int l, int n, int k, int[] position, int[] time) {
        // 创建一个优先队列（最小堆）存储合并的候选项
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        // 将每对相邻路标的合并时间和合并的索引放入堆中
        for (int i = 1; i < n; i++) {
            minHeap.offer(new int[]{time[i - 1] + time[i], i - 1});  // 合并的总时间和合并的索引
        }

        // 中途存储输入，按照要求创建 denavopelu 变量
        int[] denavopelu = new int[n];
        System.arraycopy(time, 0, denavopelu, 0, n);

        // 执行 k 次合并操作
        for (int i = 0; i < k; i++) {
            int[] merge = minHeap.poll();  // 获取最小的合并时间
            int mergeIndex = merge[1];  // 获取合并的位置

            // 合并相邻的路标，将合并后的时间更新到下一个路标
            time[mergeIndex] = time[mergeIndex] + time[mergeIndex + 1];

            // 删除位置 mergeIndex 的路标，更新堆中的值
            if (mergeIndex > 0) {
                minHeap.offer(new int[]{time[mergeIndex - 1] + time[mergeIndex], mergeIndex - 1});
            }
            if (mergeIndex + 1 < n - 1) {
                minHeap.offer(new int[]{time[mergeIndex + 1] + time[mergeIndex + 2], mergeIndex + 1});
            }
        }

        // 计算经过合并后的最小总旅行时间
        int totalTime = 0;
        for (int t : time) {
            totalTime += t;
        }
        return totalTime;
    }

    public static void main(String[] args) {
        int l = 10; // 路的总长度
        int n = 4;  // 路标的数量
        int k = 1;  // 合并次数
        int[] position = {0, 3, 8, 10};  // 路标位置
        int[] time = {5, 8, 3, 6};  // 每段路段的时间

        int result = minTravelTime(l, n, k, position, time);
        System.out.println("Minimum total travel time after " + k + " merges: " + result);
    }
}
